﻿namespace LeetCodeProject._0001_1000._101_200._101_110._105;

public class Solution
{
    public TreeNode BuildTree(int[] preorder, int[] inorder)
    {
        if (preorder == null || preorder.Length == 0)
        {
            return null;
        }

        if (inorder == null || inorder.Length != preorder.Length)
        {
            throw new ArgumentException();
        }

        var index = new InvertedIndex(inorder);
        return BuildTree(preorder, 0, inorder, 0, inorder.Length, index);
    }

    private TreeNode BuildTree(int[] preorder, int pi, int[] inorder, int ii, int count, InvertedIndex index)
    {
        if (count == 0)
        {
            return null;
        }

        var pn = index.IndexOf(preorder[pi]);
        if (pn < 0)
        {
            throw new ArgumentException();
        }

        if (pn < ii || pn >= ii + count)
        {
            throw new ArgumentException();
        }

        var leftTreeSize = pn - ii;
        var rightTreeSize = count - leftTreeSize - 1;

        return new TreeNode(preorder[pi])
        {
            left = BuildTree(preorder, pi + 1, inorder, ii, leftTreeSize, index),
            right = BuildTree(preorder, pi + 1 + leftTreeSize, inorder, pn + 1, rightTreeSize, index)
        };
    }

    class InvertedIndex
    {
        private readonly int[] _array;
        private readonly int[] _indies;

        public InvertedIndex(int[] array)
        {
            _array = (int[])array.Clone();
            _indies = new int[_array.Length];
            for (int i = 0; i < _indies.Length; i++)
            {
                _indies[i] = i;
            }

            Array.Sort(_array, _indies);
        }

        public int IndexOf(int n)
        {
            var i = Array.BinarySearch(_array, n);
            if (i >= 0)
            {
                return _indies[i];
            }

            return -1;
        }

        public bool Contains(int n) => IndexOf(n) >= 0;
    }
}